package 牛客网;

/*
 * 题目描述
有一副由NxN矩阵表示的图像，这里每个像素用一个int表示，请编写一个算法
在不占用额外内存空间的情况下(即不使用缓存矩阵)，将图像顺时针旋转90度。

给定一个NxN的矩阵，和矩阵的阶数N,请返回旋转后的NxN矩阵,保证N小于等于500，图像元素小于等于256。

测试样例：
[[1,2,3],[4,5,6],[7,8,9]],3
返回：[[7,4,1],[8,5,2],[9,6,3]]
 */
import java.util.*;
public class 不开辟新空间的像素翻转 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println("请输入N*N二维数组的N:");
		int n = sc.nextInt();
		int[][] array = new int[n][n];
		int k = 1;
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++, k++)
				array[i][j] = k;
		System.out.println("未翻转的N*N二维数组:");
		printArray(array, n);
		array = transformImage(array, n);
		printArray(array, n);
				
	}
	/*
	 * 思路：
	 * 矩阵 array如下：
	 * 		1 2 3 	               7 8 9                      7 4 1
	 * 		4 5 6    上下两部分交换 4 5 6  按照主对角线再交换   8 5 2   顺时针旋转90度完成
 	 * 		7 8 9 			       1 2 3                      9 6 3
 	 * 
 	 * 		                       7 8 9                     3 6 9 
 	 *  	...如上				 4 5 6  按照次对角线交换为  2 5 8    逆时针旋转90度完成
 	 *                             1 2 3                     1 4 7 
 	 * 总结：
 	 * 		1.顺时针旋转矩阵先上下两部分进行交换,  再按照主对角线交换
 	 * 		2.逆时针旋转矩阵先按照主对角线交换,  再进行上下两部分交换
 	 * 顺时针翻转：
 	 *      1.先翻再主     2.先次再翻
 	 * 逆时针翻转：
 	 * 		2.先翻再次     2.先主再翻
	 */
	public static int[][] transformImage(int[][] mat, int n) {
        // write code here
		int temp = 0;
		//第一步:矩阵进行上半部分与下半部分进行交换
		for(int i = 0; i < n/2; i++) {
			for(int j = 0; j < n; j++) {
				temp = mat[i][j];
				mat[i][j] = mat[n-i-1][j];
				mat[n-i-1][j] = temp;
			}
		}
		//第二步:交换过后的矩阵按照对角线再次进行交换
		for(int i = 0; i < n - 1; i++) {
			for(int j = i+1; j < n; j++) {
				temp = mat[i][j];
				mat[i][j] = mat[j][i];
				mat[j][i] = temp;
			}
		}
		return mat;
    }
	//打印矩阵
	public static void printArray(int[][] array, int n) {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				System.out.print(array[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
	}
}
